#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

//单词拆分
//没oj出来，第一个是状态转移表示的值不太好确定，用bool值
//第二个是对string和哈希方法的匹配，想不到去用
//0  到  j-1    j  到  i 这个状态转移方程真的很巧妙
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> hash;
        for (auto& v : wordDict) hash.insert(v);

        //创建dp表
        vector<bool> dp(n + 1);
        s = " " + s;

        //初始化
        dp[0] = true;
        //填表
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }

        }
        //返回值
        return dp[n];


    }
};
int main()
{

	return 0;
}